package algorithm.sorty.sort.compare;

import algorithm.sorty.Sort;

/**
 * @Description: 堆排序，是对选择排序的一种优化
 * @Author Ammar
 * @Create 2023/5/1 08:39
 */
public class HeapSort<T extends Comparable<T>> extends Sort<T> {
    private int heapSize;

    @Override
    public void sort() {
        // 原地建堆
        heapSize = array.length;
        for (int i = (heapSize >> 1) - 1; i >= 0; i--) {
            siftDown(i);
        }

        while (heapSize > 1) {
            // 交换堆顶元素和尾部元素
            swap(0, --heapSize);
            // 对0位置进行siftDown（恢复堆的性质）
            siftDown(0);
        }
    }

    /**
     * 让index位置的元素下滤
     *
     * @param index
     */
    private void siftDown(int index) {
        T element = array[index];
        int half = heapSize >> 1;
        while (index < half) {
            int childIndex = (index << 1) + 1;
            T child = array[childIndex];
            // 右子节点
            int rightIndex = childIndex + 1;
            // 选出左右子节点最大的那个
            if (rightIndex < heapSize && compare(array[rightIndex], child) > 0) {
                child = array[childIndex = rightIndex];
            }
            if (compare(element, child) >= 0) break;
            array[index] = child;
            index = childIndex;
        }
        array[index] = element;
    }

}
